package com.mesnac.sort.heap;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class AbstractHeap<T> implements Heap<T>{  
	  
    private List<T> l = new ArrayList<T>(128);  
  
    private Comparator<T> com;  
      
  
    /* 
     * 默认构造器 
     * 接受泛型的数组 
     */  
    public AbstractHeap(T[] elements)  
    {  
        init(elements);  
    }  
  
    /* 
     * 带Comparator的构造器 
     * 如果com为null会抛出IllegalArgumentException 
     */  
    public AbstractHeap(Comparator<T> com, T[] elements)  
    {  
        if (com == null)  
            throw new IllegalArgumentException("compartor can't be null");  
        this.com = com;  
        init(elements);  
    }  
  
    /* 
     * 初始化Heap中的ArrayList 
     */  
    private void init(T[] elements)  
    {  
        l.add(null);  
        for (int i = 0; i < elements.length; i++)  
        {  
            add(elements[i]);  
        }  
        System.out.println("Queue length is : " + l.size());  
        System.out.println("Content is : " + l);  
    }  
  
    /* 
     * 得到堆顶的元素 
     */  
  
    public Object get()  
    {  
        return l.get(1);  
    }  
  
    /* 
     * 移除堆顶端元素，并重新维护Heap 
     */  
 
    public T remove()  
    {  
        T toReturn = l.get(1);  
        T ret = l.get(l.size() - 1);  
        l.set(1, ret);  
        l.remove(l.size() - 1);  
          
        fixDown(1);  
  
        System.out.println("Queue length is : " + l.size());  
        System.out.println("Content is : " + l);  
        return toReturn;  
    }  
    /* 
     * 检测Heap是否为空 
     */  

    public boolean isEmpty()  
    {  
        return l.size() == 0;  
    }  
  
    /* 
     * 情况Heap中所有元素 
     */  
  
    public void clear()  
    {  
        l.clear();  
    }  
  
    /* 
     * 将堆顶元素替换，并重新维护Heap 
     */  
  
    public void set(T obj)  
    {  
        l.set(1, obj);  
        fixDown(1);  
    }  
  
    /* 
     * 向Heap中加入一个元素 
     */  
 
    public void add(T obj)  
    {  
        l.add(obj);  
        fixUP(l.size());  
    }  
  
    /* 
     * 比较器 
     */  
    protected int compare(int i, int j) throws NoComparableException  
    {  
        if (com != null)  
        {  
            return com.compare(l.get(i), l.get(j));  
        }  
        else if (l.get(j) instanceof Comparable)  
        {  
            return ((Comparable) l.get(i)).compareTo(l.get(j));  
        }  
        else  
        {  
            throw new NoComparableException(  
                    "Not implements Comparable interface.");  
        }  
    }  
  
    /* 
     * 比较器 
     */  
    protected int compare(T i, T j) throws NoComparableException  
    {  
        if (com != null)  
        {  
            return com.compare(i, j);  
        }  
        else if (i instanceof Comparable)  
        {  
            return ((Comparable) i).compareTo(j);  
        }  
        else  
        {  
            throw new NoComparableException(  
                    "Not implements Comparable interface.");  
        }  
    }  
  
    /* 
     * 向上维护 
     */  
    private void fixUP(int start)  
    {  
        int k = start - 1;  
        T s = l.get(k);  
        try  
        {  
            while (k != 1 && compare(l.get(k >> 1), s) <= 0)  
            {  
                l.set(k, l.get(k >> 1));  
                k >>= 1;  
  
            }  
        } catch (NoComparableException e)  
        {  
            e.printStackTrace();  
        }  
        l.set(k, s);  
    }  
  
    /* 
     * 向下维护 
     */  
    private void fixDown(int k)  
    {  
        T ret = l.get(k);  
        int j = k;  
        int r = j * 2;  
        int size = l.size() - 1;  
        while (r <= size)  
        {  
            try  
            {  
                if (r < size && compare(l.get(r + 1), l.get(r)) > 0)  
                    r++;  
                if (compare(l.get(r), ret) < 0)  
                    break;  
            } catch (NoComparableException e)  
            {  
                // TODO Auto-generated catch block  
                e.printStackTrace();  
            }  
            l.set(j, l.get(r));  
            j = r;  
            r *= 2;  
        }  
        l.set(j, ret);  
    }  
}  
